{
  // 将二叉树的数组结构转为真实的树结构
  // 关于二叉树的题目，网站上给的都直接是一个数组，那么本地测试的时候，就很不方便。
  function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
  }

  function array2binary(arr) {
    if (!arr || !arr.length) {
      return null;
    }

    let index = 0;
    const queue = [];
    const len = arr.length;
    const head = new TreeNode(arr[index]);
    queue.push(head);
    while (index < len) {
      const pNode = queue.shift();

      // 左节点处理
      index++;
      if (arr[index] !== null && arr[index] !== undefined) {
        const node = new TreeNode(arr[index]);
        pNode.left = node;
        queue.push(node);
      }

      // 右节点处理
      index++;
      if (arr[index] !== null && arr[index] !== undefined) {
        const node = new TreeNode(arr[index]);
        pNode.right = node;
        queue.push(node);
      }
    }
    return head;
  }

  const root = array2binary([3, 9, 20, null, null, 15, 7]);
  console.log('root: ', root);
}

{
  // 二叉树遍历（分为前序遍历、中序遍历、后序遍历、层序遍历）
  // 前序遍历：访问根节点->遍历左子树->遍历右子树
  // 中序遍历：遍历左子树->访问根节点->遍历右子树
  // 后续遍历：遍历左子树->遍历右子树->访问根节点
  // 如下二叉树：
  //       0
  //      / \
  //     1   2
  //    / \  / \
  //   3  4  5  6
  //  / \ /
  // 7  8 9
  // 前序遍历结果：0137849256
  // 中序遍历结果：7381940526
  // 后序遍历结果：7839415620
  // 层序遍历结果：0123456789

  // 法一 用递归来遍历二叉树 前中后序遍历（深度优先遍历）
  {
    var preorder = []; // 前序结果
    var inorder = []; // 中序结果
    var postorder = []; // 后序结果

    // 前序遍历是先处理节点val，在递归处理左右子树；
    // 中序遍历是先递归处理左子树，然后在处理节点val，最后递归处理右子树；
    // 后序遍历是先递归处理左右子树，然后在处理节点val；
    var loop = function (root) {
      // 当前节点为空，表示达到了叶子节点
      if (root == null) return;

      preorder.push(root.val); // 前序
      loop(root.left);
      inorder.push(root.val); // 中序
      loop(root.right);
      postorder.push(root.val); // 后序
    };

    loop(root);
    console.log('前序结果', preorder);
    console.log('中序结果', inorder);
    console.log('后序结果', postorder);
  }

  // 法二 前中后序遍历（利用栈）

  {
    // 前序遍历
    // 跟节点入栈，依此去除栈顶元素
    // 访问栈顶元素，同时出栈，将栈顶元素当作根元素，当前元素右节点入栈，左节点入栈（注意右先入后出，这是栈的特性）
    // 重复上述擦操作，直到整个栈为空，遍历结束
    var preorderTraver = function (root) {
      const stack = [root];
      const res = [];
      while (stack.length > 0) {
        const node = stack.pop(); // 栈顶取元素
        res.push(node.val);
        if (node.right) {
          stack.push(node.right); // 右节点先入栈
        }
        if (node.left) {
          stack.push(node.left); // 左元素后入栈
        }
      }
      return res;
    };
    console.log('前序遍历', preorderTraver(root));

    // 中序遍历
    // 遍历将根节点和左子树入栈
    // 直到左子树为空，访问栈顶元素，同时将栈顶元素作为根元素，并出栈
    // 开始访问右子树，循环出栈直到整个栈为空，遍历结束
    var inorderTraver = function (root) {
      const stack = [];
      const res = [];

      while (stack.length || root) {
        if (root) {
          // 遍历根节点，将根节点和左子树入栈
          stack.push(root);
          root = root.left;
        } else {
          const node = stack.pop();
          res.push(node.val);
          root = node.right;
        }
      }
      return res;
    };
    console.log('中序遍历', inorderTraver(root));

    // 后续遍历（和前序遍历思想相反）
    // 跟节点入栈，依此去除栈顶元素
    // 访问栈顶元素，同时出栈，将栈顶元素当作根元素，当前元素左节点入栈，右节点入栈（注意左先入后出，这是栈的特性）
    // 重复上述擦操作，直到整个栈为空，遍历结束
    var postorderTraver = function (root) {
      const stack = [root];
      const res = [];
      while (stack.length > 0) {
        const node = stack.pop();
        res.unshift(node.val); // 从前往后塞入数据（注意这里和前序有区别）
        if (node.left) {
          stack.push(node.left); // 左节点先入栈
        }
        if (node.right) {
          stack.push(node.right); // 右节点后入栈
        }
      }
      return res;
    };

    console.log('后序遍历', postorderTraver(root));
  }

  {
    // 层序遍历（广度优先遍历）
    var level = function (root) {
      const res = [];
      const queue = [root];

      while (queue.length > 0) {
        const node = queue.shift();
        res.push(node.val);
        if (node.left) {
          queue.push(node.left);
        }

        if (node.right) {
          queue.push(node.right);
        }
      }
      return res;
    };
    console.log('层序遍历', level(root));
  }
}

{
  // 实现函数接受任意二叉树，求二叉树所有叶子路径组成的数字之和

  // class TreeNode{
  //   value: Number,
  //   left?: TreeNode,
  //   right?: TreeNode
  // }

  // 例子 一层二叉树定义，路径包括 1 -> 2, 1 -> 3
  // const node = new TreeNode()
  // node.value = 1
  // node.left = new TreeNode()
  // node.left.value = 2
  // node.right = new TreeNode()
  // node.right.value = 3
  // getPathSum(node) // return 7 = (1 + 2) + (1 + 3)

  function getPathSum(root) {
    let num = 0;

    function addNum(node) {
      if (node.left) {
        sum += node.value + node.left.value;
        if (node.left.left) {
          addNum(node.left);
        } else if (node.left.right) {
          addNum(node.left);
        }
      }

      if (node.right) {
        sum += node.value + node.right.value;
        if (node.right.left) {
          addNum(node.right);
        } else if (node.right.right) {
          addNum(node.right);
        }
      }
    }
    addNum(root);
    console.log(num);
  }

  class TreeNode {}
  const node = new TreeNode();
  node.value = 1;
  node.left = new TreeNode();
  node.left.value = 2;
  node.right = new TreeNode();
  node.right.value = 3;
  getPathSum(TreeNode);
}

{
  // 相同的树
  // 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
  // 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
  // 示例 1：
  // 输入：p = [1,2,3], q = [1,2,3]
  // 输出：true
  // 示例 2：
  // 输入：p = [1,2], q = [1,null,2]
  // 输出：false
  // 示例 3：
  // 输入：p = [1,2,1], q = [1,1,2]
  // 输出：false

  /**
   * Definition for a binary tree node.
   * function TreeNode(val, left, right) {
   *     this.val = (val===undefined ? 0 : val)
   *     this.left = (left===undefined ? null : left)
   *     this.right = (right===undefined ? null : right)
   * }
   */
  /**
   * @param {TreeNode} p
   * @param {TreeNode} q
   * @return {boolean}
   */

  // 法一 递归
  var isSameTree = function (p, q) {
    if (p === null && q === null) return true;
    if (p === null || q === null) return false;
    if (p.val === q.val) return true;

    return (
      p.val === q.val &&
      isSameTree(p.left, q.left) &&
      isSameTree(p.right, q.right)
    );
  };

  // 法二 迭代
  // 维护一个队列，先把「整个树的比较」入列，进行一些判断后，带出「子树的比较」入列，继续出列、入列，直到没有子树可入列比较，就比较完了。
  const isSameTree = (p, q) => {
    const queue = [{ p, q }];
    while (queue.length) {
      const cur = queue.shift();
      if (cur.p == null && cur.q == null) continue;
      if (cur.p == null || cur.q == null) return false;
      if (cur.p.val != cur.q.val) return false;
      queue.push(
        {
          p: cur.p.left,
          q: cur.q.left,
        },
        {
          p: cur.p.right,
          q: cur.q.right,
        }
      );
    }
    return true;
  };

  // 法三 javascript api
  var isSameTree = function (p, q) {
    return JSON.stringify(p) === JSON.stringify(q);
  };
}

{
  // 对称二叉树
  // 给定一个二叉树，检查它是否是镜像对称的。 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
  // 示例1：二叉树[1,2,2,3,4,4,3]是对称的,返回true
  //     1
  //    / \
  //   2   2
  //  / \ / \
  // 3  4 4  3
  // 示例2：二叉树[1,2,2,null,3,null,3]则不是镜像对称的,返回false
  //     1
  //    / \
  //   2   2
  //    \   \
  //     3    3

  // 思路分析
  // 除了跟节点意外的任意节点A，只要找到关于轴的对称节点A1，若二者val相等，那么这两个节点就符合条件，如果二叉树中所有的对称节点都符合条件，那么就是对称二叉树
  // 递归处理
  // 首先我们先把检查二叉树是否对象，转化成每两个节点的对称的比较
  // 每次穿入两个比较的节点
  // 递归直到二叉树中所有节点比较完毕
  function symmetricBinaryTree(root) {
    // 如果跟节点为空返回true
    if (!root) {
      return true;
    }

    // loop函数比较两个节点是否完全相同
    function loop(left, right) {
      // 两个节点都不存在返回true
      if (!left && !right) {
        return true;
      }

      // 其中一个节点不存在或者两个节点得值不想等返回false
      if (!left || !right || left.value !== right.value) {
        return false;
      }

      // 遍历当前两个对称点的字节点的对称点
      return loop(left.left, right.right) && loop(left.right, right.left);
    }

    // 初始化传入跟节点的左右节点
    return loop(root.left, root.right);
  }
}

{
  // 对比二叉树两侧的节点数量是否相等

  // 法一 递归
  function diffTree(root) {
    if (!root) return true;

    function loop(left, right) {
      // 两个节点都不存在
      if (!left && !right) {
        return true;
      }
      // // 其中一个节点不存在
      if (!left || !right) {
        return false;
      }

      return loop(left.left, right.left) && loop(left.right, right.right);
    }
    return loop(root.left, root.right);
  }

  // 法二 利用栈
  function diffTree(root) {
    if (!root) return true;
    const leftQueue = [root.left];
    const rightQueue = [root.right];
    let result = true;

    while (leftQueue.length > 0) {
      const leftNode = leftQueue.shift();
      const rightNode = rightQueue.shift();

      if (leftNode && rightNode) {
        leftQueue.push(leftNode.left, leftNode.right);
        rightQueue.push(rightNode.left, rightNode.right);
      } else if (!leftNode && !rightNode) {
        result = true;
      } else {
        result = false;
        break;
      }
    }
    return result;
  }
}
